package com.lx.algorithm.recursion.class23;

import static com.lx.algorithm.radix.RadixSort.printArray;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-24 17:21:16
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-24     张李鑫                     1.0         1.0 Version
 */
public class SplitSumClosedSizeHalf {
    /**
     * 给定一个正数数组arr，请把arr中所有的数分成两个集合
     * 如果arr长度为偶数，两个集合包含数的个数要一样多
     * 如果arr长度为奇数，两个集合包含数的个数必须只差一个
     * 请尽量让两个集合的累加和接近
     * 返回：
     * 最接近的情况下，较小集合的累加和
     */

    public static int splitSumClosedSizeHalf(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }

        int l = arr.length;
        if ((l & 1) == 1) {
            return Math.max(process(arr, sum / 2, 0, 0, l / 2), process(arr, sum / 2, 0, 0, (l / 2) + 1));
        }
        return process(arr, sum / 2, 0, 0, l / 2);

    }

    private static int process(int[] arr, int target, int index, int sum, int l) {
        if (sum > target) {
            return Integer.MIN_VALUE;
        }

        if (index == arr.length) {
            return l == 0 ? sum : Integer.MIN_VALUE;
        }

        int p = process(arr, target, index + 1, sum + arr[index], l - 1);
        int p1 = process(arr, target, index + 1, sum, l);
        return Math.max(p1, p);
    }


    public static int dpII(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        sum = sum / 2;
        int l = (arr.length + 1) / 2;
        int[][][] dp = new int[sum + 1][arr.length + 1][l + 1];

        // dp[j][arr.length][0] = j;
        for (int j = sum; j >= 0; j--) {
            dp[j][arr.length][0] = j;
            for (int i = arr.length - 1; i >= 0; i--) {
                //只要次数没有了 当前格子就是sum
                dp[j][i][0] = j;
                for (int k = 1; k <= l; k++) {
                    int p = j + arr[i] > sum ? 0 : dp[j + arr[i]][i + 1][k - 1];
                    int p2 = dp[j][i + 1][k];
                    dp[j][i][k] = Math.max(p, p2);
                }
            }
        }
        if ((arr.length & 1) == 1) {
            return Math.max(dp[0][0][arr.length / 2], dp[0][0][arr.length / 2 + 1]);
        }
        return dp[0][0][l];
    }


    public static int[] randomArray(int len, int value) {
        int[] arr = new int[len];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * value);
        }
        return arr;
    }

    public static int dp(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        sum /= 2;
        int N = arr.length;
        int M = (N + 1) / 2;
        int[][][] dp = new int[N + 1][M + 1][sum + 1];
        for (int i = 0; i <= N; i++) {
            for (int j = 0; j <= M; j++) {
                for (int k = 0; k <= sum; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        for (int rest = 0; rest <= sum; rest++) {
            dp[N][0][rest] = 0;
        }
        for (int i = N - 1; i >= 0; i--) {
            for (int picks = 0; picks <= M; picks++) {
                for (int rest = 0; rest <= sum; rest++) {
                    int p1 = dp[i + 1][picks][rest];
                    // 就是要使用arr[i]这个数
                    int p2 = -1;
                    int next = -1;
                    if (picks - 1 >= 0 && arr[i] <= rest) {
                        next = dp[i + 1][picks - 1][rest - arr[i]];
                    }
                    if (next != -1) {
                        p2 = arr[i] + next;
                    }
                    dp[i][picks][rest] = Math.max(p1, p2);
                }
            }
        }
        if ((arr.length & 1) == 0) {
            return dp[0][arr.length / 2][sum];
        } else {
            return Math.max(dp[0][arr.length / 2][sum], dp[0][(arr.length / 2) + 1][sum]);
        }
    }


    public static void main(String[] args) {
        int maxLen = 20;
        int maxValue = 50;
        int testTime = 10000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * maxLen);
            int[] arr = randomArray(len, maxValue);
            int ans1 = dpII(arr);
            int ans2 = dp(arr);
            if (ans1 != ans2) {
                printArray(arr);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("Oops!");
                break;
            }
        }

//        //16,43,17,6,12,39,4,
//        System.out.println("测试结束");
//        int[] arr = {5, 8, 0};
//        System.out.println(dpII(arr));
    }
}
